package indexof

type KMP struct {
}

func (this KMP) indexOf(s, p string) int {

	next := GetNext(p)

	i := 0 // S 的下标
	j := 0 // P 的下标
	s_len := len(s)
	p_len := len(p)

	for i < s_len && j < p_len {
		// P 的第一个字符不匹配或 S[i] == P[j]
		if j == -1 || p[j] == s[i] {
			i++
			j++
		} else {
			// 当前字符匹配失败，进行跳转
			j = next[j]
		}
	}

	// 匹配成功
	if j == p_len {
		return i - j
	}

	return -1
}

/* P 为模式串，下标从 0 开始 */
func GetNext(P string) [] int {

	n := len(P)

	next := make([]int, n)

	i := 0 // P 的下标
	j := -1
	next[0] = -1
	for i < n-1 {
		if j == -1 || P[i] == P[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}

	return next
}

/*func main() {

	next := GetNext("abababca")

	for i, v := range next {

		fmt.Println(i, v)
	}

	fmt.Println("index : " , indexOf("bbc abcdab abcdabcdabde", "abcdabcppp"))
}*/
